/*
 * Copyright (c) 2021.版权所有高金磊
 */

package 领扣算法.AA中等题.扁平化多级双向链表;

import org.python.indexer.ast.NPass;
import 领扣算法.AA中等题.三数之和.Mian;
import 领扣算法.AA中等题.有效数独.middle;

import javax.swing.plaf.nimbus.State;
import java.util.LinkedList;
import java.util.Stack;

public class Main {

    static LinkedList<Node> nodes = new LinkedList<>();

    static Node middle;

    /**
     * 扁平化多级双向链表
     * @param head
     * @return new_head
     */
    public Node flatten(Node head) {
        //数据预处理？本身为list模式--考虑数组--发现不需要预处理（没法预处理）
        nodes.clear();
        //特殊情况预处理
        if (head == null)
            return head;
        //写逻辑
        plus(head);//因为每个node都需要做同样操作--使用递归--因为跨方法传递数据，所以声明一个类变量

        //答案数据整理
        head = nodes.poll();
        middle = head;
        middle.prev = null;
        middle.child = null;
        for (Node node : nodes) {
            middle.next = node;
            node.prev = middle;
            node.child = null;
            node.next = null;
            middle = middle.next;
        }
        return head;
    }

    private void plus(Node head) {
        if (head == null) {
            return;
        }
        nodes.addLast(head);
        plus(head.child);
        plus(head.next);
    }
}

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
